In order to improve the performance of database management systems it is desirable that several users be granted concurrent access to the same data. However, when concurrent access is allowed user activities must be carefully synchronized and coordinated to assure that a user reading the database will not receive inconsistent data, i.e., data that has been incompletely updated at the time of reading or data that has been updated after a reading operation is initiated. Synchronization of concurrent access is usually achieved through locking mechanisms. Coordination of contemporaneous activities is implemented by requiring all users to observe common protocols.
In one known locking mechanism, two types of locks are distinguished--read locks and write locks. A read lock protects the data being read from being changed during the read. A write lock assures exclusive access to the data. Using this locking mechanism a writer cannot be run concurrently with any other user and contemporaneous readers can share data provided there is no concurrently executing writer. This form of concurrency may be described as "several readers or one writer".
In many applications such a low degree of concurrency is unacceptable. For example, in a stored program controlled electronic switching system, rapid call completion may be dependent on the controlling program having free access to a database used to store system information such as the translation tables typically required for telephone systems. Delaying calls while a database update operation is being completed would result in an unnecessary degradation of system performance. A further disadvantage of "several readers or one writer" concurrency is the complexity of mechanisms which must be provided to detect deadlock conditions where two or more users are waiting for events which cannot happen.
A method for providing "several readers and one writer" concurrency is disclosed in a paper by Y. E. Lien and P. J. Weinberger entitled "Consistency, Concurrency and Crash Recovery," published in 1978 in the Proceedings of the ACM SIGMOD International Conference on Management of Data. In the disclosed method, the operations to be performed on a database are grouped into units of consistency referred to as a transaction. Each transaction has a private storage area called its work space to store copies of the entities or parts of the database accessed by that transaction. A transaction can only read data after the data is copied into the transaction's work space. The transaction can only write data into the database by first writing the data into the transaction's work space and then copying the contents of the work space into the database. Only one write transaction accessing a given entity is allowed at a time. The disclosed method also provides that the full copying of entities is not required if the database is arranged in a tree-like structure. However, in applications wherein many transactions access the same data, storing private copies of that data for each transaction represents an inefficient use of available memory resources and system real time. Further, delaying access to data being updated by a write transaction until the data is copied from work space to database adds additional complexity to the database management system to prevent access during the copying operation and, in some applications, such access delays are unacceptable. In view of the foregoing, a recognized problem in the art is implementing "several readers and one writer" controlled access to a database without adding undue complexity to the database management system and without unnecessarily burdening system resources.